package com.ljy.my_study.leetcode.主要元素;

public class TestMain {

//    数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
//
//    示例 1：
//
//    输入：[1,2,5,9,5,9,5,5,5]
//    输出：5
//             
//
//    示例 2：
//
//    输入：[3,2]
//    输出：-1
//             
//
//    示例 3：
//
//    输入：[2,2,1,1,1,2,2]
//    输出：2
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/find-majority-element-lcci
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        System.out.println(new TestMain().majorityElement(new int[]{2,2,1,1,1,2,2}));
    }

    public int majorityElement(int[] nums) {
        int prev=-1;
        int count=0;
        for(int num:nums){
            if(count==0){
                count++;
                prev=num;
            }else if(prev==num){
                count++;
            }else{
                count--;
            }
        }
        if(count>0){
            int n=0;
            for(int num:nums){
                if(num==prev){
                    n++;
                }
            }
            if(n>nums.length/2){
                return prev;
            }
        }
        return -1;
    }
}
